package newcoder_exp.justPractise;

import java.util.*;
import org.junit.*;

public class NC74 {
    //升序数组中k出现的次数
    public int GetNumberOfK1(int[] array, int k) {
        int lo = 0, hi = array.length - 1, mid;
        int left = -1;
        while (lo <= hi) {
            mid = (hi - lo) / 2 + lo;
            if (mid == 0 && array[mid] == k || array[mid] == k && array[mid - 1] < k) {
                left = mid;
                break;
            } else if (array[mid] >= k) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        lo = 0; 
        hi = array.length - 1;
        int right = -1;
        while (lo <= hi) {
            mid = (hi - lo) / 2 + lo;
            if (mid == array.length - 1 && array[mid] == k || array[mid] == k && array[mid + 1] > k) {
                right = mid;
                break;
            } else if (array[mid] <= k) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        if (left < 0 || right < 0) return 0;
        return right - left + 1;
    }

    public int GetNumberOfK(int[] array, int k) {
        int lo = 0, hi = array.length - 1, mid;
        //查找第一个比目标小的位置作为左边界
        while (lo < hi) {
            mid = (hi - lo + 1) / 2 + lo;
            if (array[mid] >= k) {
                hi = mid - 1;
            } else {
                lo = mid;
            }
        }
        int left = lo;
        lo = 0;
        hi = array.length - 1;
    //查找第一个比目标大的位置作为右边界
        while (lo < hi) {
            mid = (hi - lo) / 2 + lo;
            if (array[mid] <= k) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        System.out.println(lo + " " + left);
        if (lo - left <= 1) return -1;//不存在返回-1
        return lo - left - 1; 
    }


    @Test
    public void test() {
        //[1,2,3,3,3,3,4,5],3
        int[] nums = new int[]{1,2,3,3,3,3,4,5};
        int res = GetNumberOfK(nums, 3);
        System.out.println(res);
    }

    @Test
    public void test2() {
        int[] nums = new int[]{};
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(null);
    }

}
